package com.itheima.datastructure.binarytree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class TreeTraversal {
    public static void main(String[] args) {
        /*
                1
               / \
              2   3
             /   / \
            4   5   6
         */
//        前序遍历（根->左->右）：1 2 4 3 5 6
//        中序遍历（左->根->右）：4 2 1 5 3 6
//        后序遍历（左->右->根）：4 2 5 6 3 1
        TreeNode root = new TreeNode(
                new TreeNode(new TreeNode(4), 2, null),
                1,
                new TreeNode(new TreeNode(5), 3, new TreeNode(6))
        );
//        preOrder(root);
//        System.out.println();
//
//        inOrder(root);
//        System.out.println();
//
//        postOrder(root);
//        System.out.println();


        List[] lists = orderTraversal(root);
        System.out.println("前序:" + lists[0]); //前序遍历（根->左->右）：1 2 4 3 5 6
        System.out.println("中序:" + lists[1]); //中序遍历（左->根->右）：4 2 1 5 3 6
        System.out.println("后序:" + lists[2]); //后序遍历（左->右->根）：4 2 5 6 3 1


    }

    /**
     * <h3>前序遍历[递归]: 打印当前节点->访问左子树->访问右子树</h3>
     *
     * @param node 节点
     */
    static void preOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        //打印当前节点
        System.out.print(node.val + "\t");
        preOrder(node.left); //访问左子树
        preOrder(node.right);//访问右子树

    }

    /**
     * <h3>中序遍历[递归]：访问左子树->打印当前节点->访问右子树</h3>
     *
     * @param node 节点
     */
    static void inOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        inOrder(node.left); // 访问左子树
        System.out.print(node.val + "\t"); // 打印当前节点
        inOrder(node.right); // 访问右子树
    }

    /**
     * <h3>后序遍历[递归]：访问左子树->访问右子树 -> 打印当前节点 </h3>
     *
     * @param node 节点
     */
    static void postOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        postOrder(node.left); // 访问左子树
        postOrder(node.right); // 访问右子树
        System.out.print(node.val + "\t"); // 打印当前节点
    }


    /**
     * 使用栈遍历： 前序/中序/后序  遍历二叉树
     *
     * @param root
     * @return
     */
    /**
     * 对二叉树进行前序、中序和后序遍历（非递归方式）
     *
     * @param root 二叉树的根节点
     * @return 包含三个列表的数组，分别是前序、中序和后序遍历的结果
     */
    public static List[] orderTraversal(TreeNode root) {
        // 前序遍历结果：根 -> 左 -> 右
        List<Integer> preOrder = new ArrayList<>();
        // 中序遍历结果：左 -> 根 -> 右
        List<Integer> inOrder = new ArrayList<>();
        // 后序遍历结果：左 -> 右 -> 根
        List<Integer> postOrder = new ArrayList<>();
        // 使用栈模拟递归过程
        LinkedList<TreeNode> stack = new LinkedList<>();

        TreeNode cur = root;
        TreeNode pop = null; // 记录最近一次出栈的节点

        // 遍历整个二叉树，直到所有节点都被访问完毕
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                // 沿着左侧路径向下访问，并将节点压入栈中
                preOrder.add(cur.val); // 前序：在下降过程中记录当前节点
                stack.push(cur);
                cur = cur.left; // 继续向左子树深入
            } else {
                // 回溯阶段处理节点
                TreeNode peek = stack.peek();

                // 判断当前节点是否有右子树需要处理
                if (peek.right == null) {
                    // 当前节点无右子树，直接弹出并处理该节点
                    pop = stack.pop();
                    inOrder.add(pop.val);   // 中序：处理当前节点
                    postOrder.add(pop.val); // 后序：处理当前节点
                } else {
                    // ~ 存在右子树的情况 ~

                    if (peek.right == pop) {
                        // 表示刚从右子树返回，此时可以安全地处理当前节点
                        pop = stack.pop();
                        postOrder.add(pop.val); // 后序：完成左右子树后处理当前节点
                    } else {
                        // 准备进入右子树进行处理
                        inOrder.add(peek.val); // 中序：准备进入右子树之前先处理当前节点
                        cur = peek.right;      // 转向右子树
                    }
                }
            }
        }

        // 返回包含三种遍历顺序结果的数组
        return new List[]{preOrder, inOrder, postOrder};
    }


}
